package LeetCode;

import java.util.ArrayList;
import java.util.List;

public class LeetCode60 {
    List<List<Integer>> res = new ArrayList<>();
    boolean flag = false;
    int count = 0;
    public String getPermutation(int n, int k) {
        if (n == 0){
            return n + "";
        }
        List<Integer> list = new ArrayList<>();
        boolean[] used = new boolean[n + 1];
        dfs(n,used,list,k);
        list = res.get(k - 1);
        String s = "";
        for (Integer integer : list) {
            s += integer + "";
        }
        return s;
    }
    // 先进行一个全排列
    public void dfs(int n, boolean[] used, List<Integer> list,int k){
        if (list.size() == n){
            res.add(new ArrayList<>(list));
            if (res.size() == k){
                flag = true;
            }
            return;
        }

        for (int i = 1; i <= n; i++){
            if (!used[i] && !flag){
                list.add(i);
                used[i] = true;
                dfs(n,used,list,k);
                used[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new LeetCode60().getPermutation(3, 2));
    }
}
